\begin{section}{Desarrollo}
	\begin{subsection}{Explicación}
		\begin{subsubsection}{Introducción al problema}
			La guerra lineal consiste en dos naves situadas en el hiperespacio de $n$ dimensiones con el objetivo de desintegrarse mutuamente mediante disparos de cañones $Warp$.\\
			
			Cada turno del combate consiste en lo siguiente:
			\begin{enumerate}
			\item Nos proveen la matriz $A'$ usada por el oponente para atacarnos y el punto $d'$ donde impactó el proyectil. Con esa información debemos intentar descubrir la posición $y$ donde se encuentra situada la nave enemiga, es decir, resolver el sistema $A'y=d'$.
					
			\item Tenemos la posición a la que pretendemos disparar ($d$) y queremos conseguir una matriz de ataque $A$ tal que $Ax=d$ donde $x$ es nuestra posición.
			\end{enumerate}
		\end{subsubsection}
		\begin{subsubsection}{Estrategia}
			En cada turno nuestra estrategia consiste en lo siguiente:
			
			\begin{enumerate}
			\item Para resolver el sistema $A'y=d'$ decicimos usar métodos directos de resolución de sistemas de ecuaciones lineales. La elección se basa en que los métodos iterativos calculan $aproximaciones$ a la solución por lo que los elegiríamos sólo en el caso de no conocer un método que calcule la solución de forma $exacta$ o que este, sea muy costoso.
				\begin{itemize}
					\item \underline{Opción 1:} Buscamos la matriz inversa de A' (existe porque es parte de las reglas de la batalla) mediante el método de eliminación Gaussiana. Es decir, efectuamos a la matriz A' distintas trasformaciones lineales hasta convertirla en la matriz identidad. Al mismo tiempo hacemos dichas trasformaciones a la matriz identidad quedando en esta la inversa de A'.
					Las transformaciones consisten en triangular superior e inferiormente A' y poner $unos$ en la diagonal.
					Una vez que conocemos la inversa ($A'^{-1}$) podemos hallar la posición buscada de la siguiente manera: $y=A'^{-1}*d'$.\\
					
					\item \underline{Opción 2:} Hallamos la factorización $LU$ de $A'$ (si no existe, conseguimos $PLU$). Resolvemos el sistema $LUy=d'$. LLamamos $Ux=z$ y resolvemos usando sustitución hacia adelante el sistema $Lz=d'$. Una vez que conocemos $z$ obtenemos $x$ tal que $Ux=z$ utilizando sustitución en reversa. (Con $PLU$ es el mismo procedimiento pero permutando $d'$ según $P$).\\
					
					Elegimos este método ya que las matrices son cuadradas. Además, la implementación es sencilla y la complejidad algorítmica del método es razonable ya que se trata de un algoritmo de orden cúbico.
				\end{itemize}
			
				La exactitud con la que calculemos la posición buscada $y$ depende del número de condición de la matriz $A'$, cuanto mayor es este número menor es la precisión del resultado obtenido. Se considera que alcanzamos al rival cuando $\left|| y' - y \right|| \leq 1$, donde $y'$ es la solución encontrada.
				
				Como creemos que el adversario va a utilizar matrices mal condicionadas para atacarnos, en cada turno estaríamos calculando una posición errada de donde se encuentra. Por este motivo, decidimos usar la estrategia de disparar en el punto promedio de todas las posiciones calculadas hasta el momento del ataque (utilizando la información de los ataques previos). Esperamos de esta manera ir obteniendo cada vez mejores aproximaciones a donde se encuentra realmente.
			
			
			\item Para atacar necesitamos una matriz $A$ que al multiplicarla por nuestra posición resulte en un impacto en la posición deseada $d$. Es decir, necesitamos que $A$ cumpla $Ax=d$.
			
			Sea $n$ la dimensión de $A$.
			Dado que tenemos $n^2$ incognitas y $n$ ecuaciones, tenemos $n^2-n$ elementos de $A$ libres. Por este motivo, podemos elegir $A$ convenientemente y luego adaptarla (forzarla a cumplir $Ax=d$).			
			
			Como debemos proveer al adversario de la matriz $A$ que usemos para el ataque tenemos que idear una estrategia para que nuestra posición no sea descubierta en el siguiente turno. La estrategia consiste en generar matrices mal condicionadas que a su vez sean inversibles (esto último por reglamento). En algunos turno usamos la matriz de Hilbert multiplicada por un escalar. 
			
			Para crear una matriz mal condicionada, generamos un único vector aleatorio de dimensión $n$ que resulta en las filas de dicha matriz. De esta manera tenemos una matriz cuyas filas son linealmente dependientes, por lo que la matriz no es inversible. Luego, sumamos a los elementos de la diagonal un $epsilon$ (Ver en las pruebas (secciones \texttt{Resultados} y \texttt{Discusión}) como fue elegido) obteniendo asi una matriz inversible y mal condicionada. En este tipo de matrices el determinante tiende a $cero$, es decir, a pesar de ser inversible, esta muy cercana a dejar de serlo.
			
			Por último, para forzarla a satisfacer el sistema elegimos una columna $j$ de $A$ tal que el $j-esimo$ elemento de $x$ sea distinto de $cero$ ($x$ no es el vector nulo por precondición ya que es nuestra posición), sino los coeficientes de $A$ que pretendemos setear no tienen importancia, y consideramos incognitas sólo a los coeficientes de esa columna. Nos quedan así, $n$ incognitas y $n$ ecuaciones, por lo que podemos despejarlas y obtener la matriz final.
			
			La matriz obtenida sigue siendo inversible ya que modficamos sólo una columna de la misma y lo que hace linealmente independiente a las filas son los elementos de la diagonal.
			
			\underline{Nota:} Al momento de obtener la matriz de ataque, pedimos un número random entre el 0 y el 9, si obtenemos el 0 usamos un múltiplo de la matriz de Hilbert, sino generamos una matriz mal condicionada como explicamos previamente.
			\end{enumerate}
		\end{subsubsection}
	\end{subsection}
	\begin{subsection}{Implementación}
		En primer lugar el desarrollo consistió en implementar módulos para las operaciones entre Matrices y Vectores que fueran necesarias para resolver sistemas lineales. Esto implicaba también implementar el algoritmo de factorización LU y el algoritmo de eliminación Gaussiana ambos con pivoteo parcial (intercambia filas para dividir por el número de mayor módulo de la columna) para resolver el sistema lineal.\\
		
		Escribimos el módulo \texttt{Matrix} que implementa una matriz en $\mathbb{R}^{nxn}$ con las siguientes operaciones:\\
		
		\begin{tabular}{rl}
			\texttt{Eliminación Gaussiana} & Eliminacion Gaussiana con pivoteo parcial.\\
			\texttt{LU} & Factorización LU con pivoteo parcial.\\
			\texttt{Inversa} & Matriz inversa con el método de Gauss.\\
			\texttt{K} & Número de condición.\\
			\multicolumn{2}{l}{
				\texttt{Suma, Resta, Multiplicación, Multiplicación por escalar, traspuesta}
			}
		\end{tabular}\\
		
		Usamos pivoteo parcial tanto para la eliminación Gaussiana como para la factorización LU para reducir el error de redondeo en las operaciones.\\
		
		Además escribimos la clase \texttt{Vector} que implementa un vector en $\mathbb{R}^n$ con las operaciones básicas como \texttt{Suma, Resta,
		Producto Escalar, Producto Vectorial, Normas}, etc.\\
		
		\underline{NOTA:} Ambas clases heredan de una clase \texttt{MatrixBase} que implementa las funciones básicas como son la suma, resta, multiplicación, etc.\\
		
		Teniendo la base (matrices, vectores y las operaciones entre ellos) implementamos una clase para la resolución de sistemas de ecuaciones lineales y una clase para elegir la matriz de ataque.\\
		
		El módulo \texttt{linearSystem} implementa las siguientes funciones:\\
		
		\begin{tabular}{rl}
			\texttt{Resolución por inversa} & consigue la inversa y hace la multiplicación.\\
			\texttt{Resolución por LU} & consigue LU (PLU) y despeja el sistema usando\\
									   & sustitución hacia adelante y sustitución reversa.\\
		\end{tabular}\\
		
		El módulo \texttt{warpCannon} implementa las siguientes funciones:\\
		
		\begin{tabular}{rl}
			\texttt{Atacar} & consigue la posición de impacto deseada y arma la matriz correspondiente.\\
		\end{tabular}\\
		
		Esta clase tiene un método privado que calcula la posición del enemigo.
		
		Nuestra primer idea fue hacer un promedio coordenada a coordenada dandole una prioridad distinta a cada vector (posición), dicha prioridad dependía del número de condición de la matriz que uso el oponente en ese turno. Es decir, $y$ tiene mayor prioridad que $z$ si y sólo si $K(A')<K(A)$ siendo $A'y=d'$ y $Az=d$.
		
		Para lograr esto, teníamos un $array$ de $tuplas$ donde la primer coordenada correspondía al vector y la segunda al número de condición de la matriz asociada.
		
		La idea finalmente implementada es una versión más simple (por cuestiones de tiempo), que sólo toma el promedio sin asignar prioridades. Igualmente quedó implementado con $tupla$ (ignorando la segunda coordenada).
	\end{subsection}
	\begin{subsection}{Ideas descartadas}
		Nuestra primer estrategia consistía en atacar con la matriz de Hilbert de orden $n$ una cierta cantidad de turnos (que pensabamos decidir mediante pruebas) y guardar en cada turno la posición del enemigo calculada. Una vez cumplida esa cantidad de turnos, sacar un promedio entre la información obtenida y disparar a esa posición sin ningún tipo de defensa.
		
		La ventaja de esta estrategia es que evitabamos tener que generar matrices mal condicionadas (ya que usabamos siempre la de Hilbert).
		
		La desventaja es que al estar atacando siempre con la misma matriz o un múltiplo de esta, el oponente estaría siempre calculando la misma posición (punto de ataque) y no generaríamos nueva información al recibir los datos. Esta conclusión es válida si y solo si el oponente posee como estrategia invertir la matriz pasada como parámetro y atacar a esa posición siempre de la misma forma. Como no podemos afirmar que esta estrategia no sea utilizada, esta idea fue descartada.
		
		Se propuso una mejora a este sistema, la cual fue generar matrices aleatoreas mal condicionadas distintas de la matriz de Hilbert o un múltiplo de ella. La idea entonces se mantenía; se enviarían matrices mal condicionadas, apuntando siempre a cualquier lugar, hasta tener información suficiente sobre la posición del contraincante para atacar. Nos pareció una idea viable, siempre que el enemigo no tenga la misma estrategia que nosotros, ya que de ser así, no recolectaríamos ningún tipo de información útil.
		
		Posterior a la última opción mencionada, encontramos la forma de generar matrices mal condicionadas que apunten a donde nosotros querramos, pudiendo evitar (o por lo menos intentar evitar) que nuestra posición sea develada al momento de atacar. De esta forma la estrategía de disparar a cualquier lado pierde sentido, ya que siempre se le envía matrices diferentes (por lo tanto siempre se obtiene información diferente y potencialmente útil) y atacar no implica necesariamente exponer nuestra posición real.	\end{subsection}
\end{section}
